package com.fwpsl.graph;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/3/26
 * @description: 图有顶点和边组成
 */
public class Graph<T> {
    private List<Vertex<T>> vertices;

    public Graph() {
        this.vertices = new LinkedList<>();
    }

    /**
     * 添加顶点
     *
     * @param data
     */
    public Vertex<T> addVertex(T data) {
        if (!vertices.contains(data)) {
            Vertex<T> vertex = new Vertex(data);
            vertices.add(vertex);
            return vertex;
        }

        return getVertex(data);
    }

    /**
     * 添加有向图的边
     *
     * @param source
     * @param destination
     */
    public void addEdge(T source, T destination) {
        addEdge(source, destination, 1d);
    }

    /**
     * 添加有向图的边
     *
     * @param source
     * @param destination
     * @param weight
     */
    public void addEdge(T source, T destination, double weight) {
        if (source == null || destination == null) {
            System.out.println("One or both of the vertices don't exist");
        }

        Vertex<T> sv = getVertex(source);
        if (sv == null) {
            sv = addVertex(source);
        }

        Vertex<T> dv = getVertex(destination);
        if (dv == null) {
            dv = addVertex(destination);
        }

        sv.addEdge(new Edge(sv, dv, weight));
    }

    /**
     * 添加边
     *
     * @param source
     * @param destination
     * @param weight
     */
    public void addEdge(Vertex<T> source, Vertex<T> destination, double weight) {
        if (source != null && destination != null) {
            source.addEdge(new Edge(source, destination, weight));
            destination.addEdge(new Edge(destination, source, weight));
        } else {
            System.out.println("One or both of the vertices don't exist");
        }
    }

    /**
     * 构建图
     *
     * @param graphEdgeArr
     * @return
     */
    public static Graph<Integer> buildIntGraph(int[][] graphEdgeArr) {
        Graph<Integer> graph = new Graph<>();
        for (int i = 1; i <= graphEdgeArr.length; i++) {
            graph.addVertex(i);
        }

        for (int i = 0; i < graphEdgeArr.length; i++) {
            Vertex<Integer> source = graph.getVertex(i + 1);
            for (int j = 0; j < graphEdgeArr[i].length; j++) {
                if (graphEdgeArr[i][j] > 0) {
                    Vertex<Integer> destination = graph.getVertex(j + 1);
                    graph.addEdge(source, destination, graphEdgeArr[i][j]);
                }
            }
        }

        return graph;
    }

    /**
     * 获取首个顶点
     *
     * @return
     */
    public Vertex<T> getFirstVertex() {
        return vertices.get(0);
    }

    /**
     * 获取顶点数量
     *
     * @return
     */
    public Integer getVertexNum() {
        return vertices.size();
    }

    /**
     * 获取边集
     *
     * @return
     */
    public List<Edge<T>> getEdges() {
        List<Edge<T>> edges = new ArrayList<>();
        for (Vertex<T> vertex : vertices) {
            edges.addAll(vertex.edges);
        }
        return edges;
    }

    /**
     * 获取顶点集
     *
     * @return
     */
    public List<Vertex<T>> getVertices() {
        return vertices;
    }

    /**
     * 根据顶点内容，获取顶点对象。
     *
     * @param data
     * @return
     */
    public Vertex<T> getVertex(T data) {
        if (data == null) {
            return null;
        }

        for (Vertex<T> v : vertices) {
            if (data.equals(v.data)) {
                return v;
            }
        }

        return null;
    }

    /**
     * 顶点的入度值
     *
     * @return
     */
    public HashMap<Vertex<T>, Integer> getInDegreMap() {
        HashMap<Vertex<T>, Integer> inDegreMap = new HashMap<>();
        for (Vertex<T> vertex : vertices) {
            inDegreMap.put(vertex, inDegreMap.getOrDefault(vertex, 0));
            for (Edge<T> edge : vertex.getEdges()) {
                inDegreMap.put(edge.getDestination(), inDegreMap.getOrDefault(edge.getDestination(), 0) + 1);
            }
        }

        return inDegreMap;
    }

    /**
     * 顶点的出度值
     *
     * @return
     */
    public HashMap<Vertex<T>, Integer> getOutDegreMap() {
        HashMap<Vertex<T>, Integer> outDegreMap = new HashMap<>();
        for (Vertex<T> vertex : vertices) {
            outDegreMap.put(vertex, vertex.getEdges().size());
        }

        return outDegreMap;
    }

    /**
     * 打印节点
     *
     * @param vertices
     * @param <T>
     * @return
     */
    public static <T> String printVerties(List<Vertex<T>> vertices) {
        if (vertices == null || vertices.isEmpty()) {
            return "";
        }

        StringJoiner sj = new StringJoiner("->");
        vertices.stream().forEach(v -> sj.add(String.valueOf(v.data)));
        return sj.toString();
    }
}
